//实现一个 MyCalendar 类来存放你的日程安排。如果要添加的日程安排不会造成 重复预订 ，则可以存储这个新的日程安排。
//
// 当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生 重复预订 。
//
// 日程可以用一对整数 startTime 和 endTime 表示，这里的时间是半开区间，即 [startTime, endTime), 实数 x 的范围为
//， startTime <= x < endTime 。
//
// 实现 MyCalendar 类：
//
//
// MyCalendar() 初始化日历对象。
// boolean book(int startTime, int endTime) 如果可以将日程安排成功添加到日历中而不会导致重复预订，返回 true 。
//否则，返回 false 并且不要将该日程安排添加到日历中。
//
//
//
//
// 示例：
//
//
//输入：
//["MyCalendar", "book", "book", "book"]
//[[], [10, 20], [15, 25], [20, 30]]
//输出：
//[null, true, false, true]
//
//解释：
//MyCalendar myCalendar = new MyCalendar();
//myCalendar.book(10, 20); // return True
//myCalendar.book(15, 25); // return False ，这个日程安排不能添加到日历中，因为时间 15 已经被另一个日程安排预订了
//。
//myCalendar.book(20, 30); // return True ，这个日程安排可以添加到日历中，因为第一个日程安排预订的每个时间都小于 20
// ，且不包含时间 20 。
//
//
//
// 提示：
//
//
// 0 <= start < end <= 10⁹
// 每个测试用例，调用 book 方法的次数最多不超过 1000 次。
//
//
// Related Topics 设计 线段树 数组 二分查找 有序集合 👍 326 👎 0


package LeetCode.editor.cn;

import java.util.TreeSet;

/**
 * @author ldltd
 * @date 2025-01-02 22:11:54
 * @description 729.我的日程安排表 I
 */
public class MyCalendarI{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 MyCalendarI fun=new MyCalendarI();


	 }

//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class MyCalendar {
    /*
        内存超
    boolean[]ar=new boolean[1000000000];
    public MyCalendar() {
    }
    public boolean book(int startTime, int endTime) {
        for (int i = startTime; i < endTime; i++) {
            if(!ar[i]){
                return false;
            }
        }
        for (int i = 0; i < endTime; i++) {
            ar[i]=true;
        }
        return true;
    }*/

   /*

   //暴力1
   List<List<Integer>> date;
    public MyCalendar() {
        date=new ArrayList<>();
    }
    public boolean book(int startTime, int endTime) {
        for (List<Integer> list : date) {
            if(startTime<list.get(1)&&endTime>list.get(0)) return false;
        }
        date.add(List.of(startTime,endTime));
        return true;
    }*/


   //利用TreeSet，可以自定义排序，用ceiling  lower 等api取值二分
   TreeSet<int[]> booked;

    public MyCalendar() {
        booked = new TreeSet<int[]>((a, b) -> a[0] - b[0]);
    }

    public boolean book(int start, int end) {
        if (booked.isEmpty()) {
            booked.add(new int[]{start, end});
            return true;
        }
        int[] tmp = {end, 0};
        //TreeSet的ceiling方法用于获取大于等于给定元素的最小元素
        int[] arr = booked.ceiling(tmp);
        //如果arr存在且不是第一个，则只需要考虑arr前一个元素和arr之间能否插入即可，即lower(tem)
        int[] prev = arr == null ? booked.last() : booked.lower(arr);
        //如果插入位置是第一个元素之前
        //或者找到的开始时间小于给定结束时间的区间的结束时间小于等于这次的开始时间，则可以插入
        //lower 返回树集合中小于指定元素的最大元素
        if (arr == booked.first() || booked.lower(tmp)[1] <= start) {
            booked.add(new int[]{start, end});
            return true;
        }
        return false;
    }
 /*
  //基于重写比较方法
  private TreeSet<int[]> booked;

    public MyCalendar() {
        booked = new TreeSet<>((a, b) -> {
            if (a[0] >= b[1]) {
                return 1;
            } else if (a[1] <= b[0]) {
                return -1;
            }
            return 0;
        });
    }

    public boolean book(int startTime, int endTime) {
        //如果比较器返回0，TreeSet认为新元素与已有元素等价（即存在冲突），不会添加。
        return booked.add(new int[] { startTime, endTime });
    }*/

}

/**
 * Your MyCalendar object will be instantiated and called as such:
 * MyCalendar obj = new MyCalendar();
 * boolean param_1 = obj.book(startTime,endTime);
 */
//leetcode submit region end(Prohibit modification and deletion)

}
